package com.codes.patch.utils;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class LISUtil {

	public static int binarySearchHigh(List<Integer> sequence, int value) {
		if (sequence.isEmpty() || sequence.get(sequence.size() - 1) < value) {
			return sequence.size();
		}
		if (sequence.size() < 3) {
			for (int i = 0; i < sequence.size(); ++i) {
				if (sequence.get(i) >= value) {
					return i;
				}
			}
			return sequence.size();
		}
		
		int left = 0;
		int right = sequence.size() - 1;
		int mid = left;
		while (left < right) {
			mid = ((left + right) >> 1);
			if (sequence.get(mid) < value) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		return left;
	}
	
	public static void LIS(List<Integer> sequence, List<Integer> answerPosition) {
		List<Integer> pre = new ArrayList<>();
		List<Integer> ins = new ArrayList<>();
		List<Integer> pos = new ArrayList<>();
		for (int i = 0; i < sequence.size(); ++i) {
			int value = sequence.get(i);
			int p = binarySearchHigh(ins, value);
			if (p >= ins.size()) {
				pre.add(p == 0 ? -1 : pos.get(pos.size() - 1));
				ins.add(value);
				pos.add(i);
			} else {
				ins.set(p, value);
				pre.add(pre.get(pos.get(p)));
				pos.set(p, i);
			}
		}
		int end = pos.get(pos.size() - 1);
		while (end != -1) {
			answerPosition.add(end);
			end = pre.get(end);
		}
		answerPosition.sort(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o1 - o2;
			}
		});
	}
}
